Stockholm, 1994

   IOI. 16 (Autobuze). Un om soseste la statia de autobuz la ora 12.00 si sta aici pna la
12.59. In statii sosesc autobuze de pe diverse trasee; omul nostru noteaza fiecare timp de sosire. Se
stie ca:
- autobuzele de pe fiecare traseu sosesc la intervale regulate de timp; sunt cel mult 17 trasee;
- n intervalul 12.00-12.59 fiecare traseu are cel putin doua opriri n statie;
- n acelasi moment pot opri autobuze de pe mai multe trasee;
- pot fi trasee care au acelasi timp de sosire si/sau aceeasi perioada ntre doua opriri succesive. Daca
exista doua rute cu acelasi timp de plecare si aceeasi perioada, ele sunt distincte.
              Se cere sa se determine cel mai mic numar de trasee de autobuz care au oprire n statie. Pentru
fiecare astfel de traseu sa se precizeze prima oprire din intervalul 12.00-12.59 precum si intervalul
dintre doua opriri.
Intrare: Fisierul de intrare contine numarul n (2n300) care arata cte autobuze au oprit n statie;
el este urmat de toti timpii de sosire, scrisi n ordine crescatoare.
Iesire: Fisierul de iesire va avea cte o linie pentru fiecare traseu. Pe ea se afla momentul sosirii
primului autobuz si intervalul de timp (n minute). Ordinea de scriere a traseelor este arbitrara. Daca
sunt mai multe solutii, se cere numai una.      
Exemplu: La intrarea
17
0 3 5 13 13 15 21 26 27 29 37 39 39 45 51 52 53
iesirea este:
0 13
3 12
5 8
==========================================
Solutia 1 (Vlad Atanasiu):
uses crt;
var a:array[1..300] of byte;
    folosit:array[1..300] of boolean;
    solutie,vector:array[1..100] of integer;
    i,tminim,nr_autobuze:integer;

function verifica(t,n:integer):boolean;
var i,j:integer;
    gasit:boolean;
begin
gasit:=true;
i:=a[t]; { i este timpul opririi t }
j:=1;
while (i<=59) and gasit do
      begin
      { daca nu exista oprirea cu timpul i }
      gasit:=false;
      while (j<=nr_autobuze) and (not gasit) do
            if (a[j]=i) and (not folosit[j]) then gasit:=true
            else inc(j);
      i:=i+n;
      end;
{ anunta daca au fost gasite toate opririle }
verifica:=gasit;
end;

function opriri:integer;
{ Intoarce numarul primei opriri nestudiate sau 0 daca nu exista }
var i:integer;
begin
i:=1;
while (folosit[i]) and (i<=nr_autobuze) do i:=i+1;
if i>nr_autobuze then opriri:=0
else opriri:=i;
end;

procedure marcheaza(t:integer);
var i:integer;
begin
tminim:=t;
for i:=1 to t do solutie[i]:=vector[i];
end;

procedure cauta(t:integer);
var n,i,j:integer;
begin
n:=1;
while (n<=30) do
      begin
      vector[t]:=n;
      { daca traseul cu prima oprire la momentul a[t] si perioada n verifica }
      if verifica(t,n) then
         begin
         { ii marcheaza opririle ca folosite }
         i:=a[t];
         j:=t;
         while i<=59 do
               begin
               while (j<=nr_autobuze) and (a[j]<>i) do inc(j);
               if j<=nr_autobuze then
               if not folosit[j] then
                  begin
                  folosit[j]:=true;
                  i:=i+n;
                  end
               else j:=j+1;
               end;
         { daca mai exista opriri }
         j:=opriri;
         { repeta procedura pentru urmatoarea oprire }
         if j<>0 then cauta(j)
         { altfel marcheaza solutia }
         else if t<tminim then marcheaza(t);
         { demarcheaza opririle }
         i:=a[t];
         j:=t;
         while i<=59 do
               begin
               while (j<=nr_autobuze) and (a[j]<>i) and (a[j]<=i) do inc(j);
               if folosit[j] then
                  begin
                  folosit[j]:=false;
                  i:=i+n;
                  end
               else j:=j+1;
               end;
         end;
      inc(n);
      end;
end;

begin
clrscr;
assign(input,'input.i16');
reset(input);
readln(input,nr_autobuze);
for i:=1 to nr_autobuze do
    begin
    read(a[i]);
    folosit[i]:=false;
    end;
tminim:=17;
cauta(1);
for i:=1 to tminim do writeln(a[i],' ',solutie[i]);
close(input);
end.
========================================
Solutia 2 (Vasile Butnaru, Timisoara):
    Solutia este urmatoarea(dupa parerea mea):
  se incearca partitionarea celor n sosiri ale autobuzelor in
  cat mai putine linii. Pentru a avea timp de rulare mic, incercam
  sa partitionam toate sosirile unei linii, daca nu e posibil
  incrementam cu 1 si incercam pentru doua linii,...
    Daca am ajuns la (n div 2)+1 linii, nu mai e posibil sa
  partitionam.
    Datele folosite:
      - variabila "au" semnifica numarul de linii in care ne
        propunem sa clasificam.
      - sol spune daca s-a gasit solutie, initial falsa.
      - in vectorul p, p[i] semnifica fapt. ca a i-a sosire este
        atribuita liniei p[i]
      - vectorul po este folosit pentru a retine solutia optima
        pentru vect. p
      - vect. t, t[i]= a i-a sosire se produce la timpul t[i]
        (datele de intrare)
      - vect. x, x[i]=pt. linia i s-au atribuit x[i] linii in orice
        moment, folositor in timpul recursiei pt. a nu face pasi
        inutili
      - vect. y, y[i]=pt. linia i, perioada este y[i].
      - vect. yo, yo[i] este y[i] pentru solutia optima
    Desi pare ca sunt prea multe siruri,nu se pune problema spatiului
 ci a timpului de rulare, vectorii x,y,yo,p,po optimizeaza recursia.
    Pt. exemplul
17
0 3 5 13 13 15 21 26 27 29 37 39 39 45 51 52 53
solutia este
0 13
3 12
5 8
 , si e gasita imediat.

const
	maxim		=	300;
	auto		=	17;
type
	atom		=	integer;
	vector		=	array [1..maxim] of atom;
var
	au,i,j,k,l,m,n		:	atom;
	y,yo,x,t,p,po		:	vector;
	sol			:	boolean;

function min(a,b:atom):atom;
 begin if a<b then min:=a else min:=b; end;

function max(a,b:atom):atom;
 begin if a>b then max:=a else max:=b; end;

procedure part(niv,unde:atom);
                     {niv=nivelul de recursie si sosirea pt.
                      care se face partitionarea, unde=ultima
                      linie pana la care s-a facut part. pana
                      in prezent, initial 0.
                     }
  var i,j:atom;
  label next;
 begin
	if niv=n+1 then
	begin
         {daca am partitionat deja toate sosirile, si pe fiecare
           linie se afla cel putin doua autobuze, atunci retinem
           solutia si parasim toate recursiile
          }
		for i:=1 to unde do if x[i]<2 then exit;
		sol:=true;
		au:=unde;
		for i:=1 to n do
		begin
			po[i]:=p[i];
			yo[i]:=y[i];
		end;
	end else
	begin
		j:=unde+1;
         {sosirea niv poate sa apartina liniilor de la 1 la unde+1
                  }
		for i:=1 to min(j,au-1) do
                                   {min()=utila pt. a situatia
                                    in care am dori sa part.
                                    pe o linie care nu exista
                                    pana in prezent
                                   }
		begin
			p[niv]:=i;
                        {sosirea niv apartine liniei i}
			inc(x[i]);
                        {avem grija ca pe linia i mai se afla
                         un autobuz}
			if x[i]>=2 then
			begin
                        {daca deja sunt >=2 sosiri testam care este
                         sosirea anterioara}
				k:=niv;
				repeat dec(k); until p[k]=i;
			end;
			if x[i]=2 then
			begin
                        {daca sunt exact doua at. retinem perioada
                        liniei, iar daca aceasta e 0 abandonam ideea}
				y[i]:=t[niv]-t[k];
				if y[i]=0 then goto next;
			end;
			if (x[i]<2) or (y[i]=t[niv]-t[k])
				then part(niv+1,max(unde,i));
                   {daca sunt mai putin de 2 sosiri pe acea linie
                    sau sunt cel putin doua si diferenta dintre
                    actuala sosire si cea anterioara este egala cu
                    perioada liniei, at. pornim mai departe...}
		next:
			dec(x[i]);
			if x[i]<2 then y[i]:=0;
                {avem grija ca pe linia i o sosire e mai putin
                ,iar daca nu mai sunt doua sos. at. nu exista
                perioada liniei}
		end;
	end;
 end;

begin
	assign(input,'input.txt'); reset(input);
	assign(output,'output.txt'); rewrite(output);
	readln(n);
	for i:=1 to n do read(t[i]); {citim timpii de sosire}
	close(input);
	sol:=false;
	au:=0;
	repeat {de aici...}
		inc(au);
		for i:=1 to n do begin x[i]:=0; y[i]:=0; end;
		part(1,0);
	until (sol) or (au=(auto div 2)+1);
           {..si pana aici incercam cu "au" linii de autobuze }
	if sol then begin
	for i:=1 to au do
	  begin
		j:=0; repeat inc(j); until po[j]=i;
		writeln(t[j],' ',yo[i]);
	  end; end;
	close(output);
end.
===============================================
Test:
17
0 3 5 13 13 15 21 26 27 29 37 39 39 45 51 52 53
